package gsw.tool.arithmetic;

import gsw.tool.common.ToolShow;

/**
 * 蛮力法（brute force method，也称为穷举法或枚举法）是一种简单直接地解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法。但是，用蛮力法设计的算法时间特性往往也是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的 。
 * 常见的蛮力法：冒泡排序、选择排序。
 *
 * @author GSW
 */
public class BruteFroce {

    public static void test() {
        //测试冒泡排序
        Card[] arr = {new Card(17, 3), new Card(11, 4),
                new Card(21, 1), new Card(4, 2), new Card(9, 3),
                new Card(3, 2), new Card(6, 4)};
        BruteFroce.bubbleSort(arr);
        ToolShow.printArr(arr);

        //测试选择排序
        Integer[] arr2 = {2121, 46364, 66, 20, 9, 71, 17};
        BruteFroce.selectSort(arr2);
        ToolShow.printArr(arr2);

    }

    /**
     * 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名“冒泡排序”。
     * 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
     * 冒泡排序是稳定的排序算法，适合少量数据的排序（10张以内），比如炸金花。
     *
     * @param arr 需要排序的数组
     */
    public static <E extends Comparable<E>> void bubbleSort(E[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        //从小到大排序
        for (int i = 0; i < arr.length - 1; i++) {
            // 判断是否排好序:可能在遍历完之前就已经排好序了
            boolean flag = true;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                E temp = arr[j];
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                return;
            }
        }
    }

    /**
     * 选选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
     * 选择排序是不稳定的排序方法（比如序列[5， 8， 3]第一次就将[5]与[3]交换，导致5挪动到8后面）。选择排序的移动次数较少，适合少量数据的排序（10~20）。
     *
     * @param arr
     */
    public static <E extends Comparable<E>> void selectSort(E[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        for (int i = 0; i < arr.length - 1; i++) {
            //先找到最值
            int index = i;
            for (int j = i + 1; j < arr.length; j++) {
                E temp = arr[index];
                if (temp.compareTo(arr[j]) > 0) {
                    index = j;
                }
            }

            //然后与最值交换
            if (index != i) {
                E temp = arr[i];
                arr[i] = arr[index];
                arr[index] = temp;
            }
        }
    }

    /**
     * 模拟卡牌
     *
     * @author GSW
     */
    public static class Card implements Comparable<Card> {
        int cardPoint;// 点数
        int cardColor;// 花色

        public Card(int cardPoint, int cardColor) {
            super();
            this.cardPoint = cardPoint;
            this.cardColor = cardColor;
        }

        @Override
        public String toString() {
            return "Card [点数=" + cardPoint + ", 花色=" + cardColor + "]";
        }

        @Override
        public int compareTo(Card c) {
            if (c == null) {
                return 1;
            }

            if (cardPoint > c.cardPoint) {
                return 1;
            } else if (cardPoint < c.cardPoint) {
                return -1;
            } else {
                if (cardColor > c.cardColor) {
                    return 1;
                } else if (cardColor < c.cardColor) {
                    return -1;
                } else {
                    return 0;
                }
            }

        }
    }
}
